package a2023.a0306;

/**
 * @author lenovo
 * @date 2023/1/31
 */
public class a {


    public static void main(String[] args) {
        System.out.println(minimumDeletions("bbaaaaabbb"));
    }

    public static int minimumDeletions(String s) {
        int countB = 0, dp = 0;  // 令dp表示将s[0,i]变平衡最少需要删除的次数
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == 'a') {
                dp = Math.min(dp + 1, countB);  // 末尾出现a的时候，2个选择：1、删除这个a，然后将s[0,i-1]变平衡；2、保留这个a，删除前面所有的b
            }
            else {
                ++countB;  // 出现b的时候，最后面的b不需要删除，dp不变，b的个数加1就好
            }
        }
        return dp;
    }
}










